﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Sets = Algoritmia.DataStructures.Sets;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ShortestPaths.Positive
{
    public class DijkstraShortestPathsFinder<T> : IShortestPathsFinder<T,double>
    {
        protected readonly Func<IEnumerable<T>,IMap<T, double>> _createDistanceMap;
        protected readonly Func<IEnumerable<T>, Sets.ISet<T>> _createSet;
        protected readonly Func<IEnumerable<T>, IMap<T, T>> _createBackpointersMap;

        public DijkstraShortestPathsFinder(Func<IEnumerable<T>,IMap<T,double>> createDistanceMap = null,
                                          Func<IEnumerable<T>, IMap<T, T>> createBackpointersMap = null,   
                                          Func<IEnumerable<T>,Sets.ISet<T>> createSet = null)
        {
            _createDistanceMap = createDistanceMap ?? (v => AlgoritmiaFactory.Maps<T, double>.Default);
            _createBackpointersMap = createBackpointersMap ?? (v => AlgoritmiaFactory.Maps<T, T>.Default);
            _createSet = createSet ?? (v => AlgoritmiaFactory.Sets<T>.Default);
        }

        #region IShortestPathFinder<T,double> Members

        public IEnumerable<KeyValuePair<T,T>> SomeToSomeBackpointers(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var distances = _createDistanceMap(g.V);

            foreach (var v in g.V)
            {
                distances[v] = double.PositiveInfinity;
            }
            var inFringeFrom = _createBackpointersMap(g.V);
            foreach (var s in sources)
            {
                distances[s] = 0.0;
                inFringeFrom[s] = s;
            }

            var added = _createSet(g.V);
            int left = targets.Count();
            while (inFringeFrom.Count > 0 && left > 0)
            {
                var keyValuePair = inFringeFrom.ArgMin(kv => distances[kv.Key]);
                var v = keyValuePair.Key;
                inFringeFrom.Remove(v);
                added.Add(v);
                yield return keyValuePair;

                if (targets.Contains(v))
                {
                    left--;
                }

                if (left > 0)
                {
                    foreach (var s in g.Successors(v))
                    {
                        if (!added.Contains(s) && distances[v] + d(v, s) < distances[s])
                        {
                            inFringeFrom[s] = v;
                            distances[s] = distances[v] + d(v, s);
                        }
                    }
                }

            }
        }

        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var distances = _createDistanceMap(g.V);
            var minimumDistance = double.PositiveInfinity;
            foreach (var v in g.V)
            {
                distances[v] = minimumDistance;
            }
            var inFringeFrom = _createBackpointersMap(g.V);
            foreach (var s in sources)
            {
                distances[s] = 0.0;
                inFringeFrom[s] = s;
            }

            var added = _createSet(g.V);
            int left = targets.Count();
            while (inFringeFrom.Count > 0 && left > 0)
            {
                var keyValuePair = inFringeFrom.ArgMin(kv => distances[kv.Key]);
                var v = keyValuePair.Key;
                inFringeFrom.Remove(v);
                added.Add(v);

                if (targets.Contains(v))
                {
                    left--;
                    if (minimumDistance > distances[v])
                    {
                        minimumDistance = distances[v];
                    }
                }

                if (left > 0)
                {
                    foreach (var s in g.Successors(v))
                    {
                        if (!added.Contains(s) && distances[v] + d(v, s) < distances[s])
                        {
                            inFringeFrom[s] = v;
                            distances[s] = distances[v] + d(v, s);
                        }
                    }
                }

            }
            return minimumDistance;
        }

        #endregion
    }
}
